The disclosure generally relates to the field of distributed storage systems, and more particularly to data repair in distributed storage systems.
Distributed storage systems can use replication type redundancy for data resilience (i.e., creating and maintaining duplicates of data) or erasure coding type redundancy which has greater storage efficiency. Erasure coding for a distributed storage system involves splitting a data unit (e.g., a file) of size B into x chunks, each of the same size B/x. An erasure code is then applied to generate parity information, which introduces some redundancy of the file. The encoding results in n fragments of the file when the parity information fragments are included. The erasure code applied to the data is denoted as (n, k), where n represents the total number of nodes across which all fragments will be stored and k represents the number of systematic nodes (i.e., nodes that store only systematic data or non-parity information). The number of parity nodes (i.e., nodes that store parity information) is n−k=r.
With the substantial increase in the amount of data being stored, research into erasure codes seeks to optimize this storage efficiency along with reliability. Some of this research has explored a class of erasure codes referred to as maximum distance separable (MDS) codes (e.g., Reed Solomon codes). Since a distributed storage system will suffer erasures (e.g., storage node failures) due to various reasons (e.g., lower cost, unreliable storage nodes), research attempts to address the problem/cost of data transmission across a network to recover from an erasure and of the amount of data stored at each node, which has been referred to as a “repair problem.” Research into this repair problem has led to “regeneration codes” or “regenerating codes.” These codes are erasure codes which allow for repair of a failed node more efficiently than a traditional erasure code. Regenerating codes satisfy the expression:B≤Σi=0k−1min{α,(d−i)β}  (Equation 1) (in the case of a functional-repair), with the parameters defined as:    B=total size of the source data to be stored, in terms of number of symbols;    α=storage capacity of each node, in terms of number of symbols;    k=the source data is recoverable from the data in any k nodes;    d and β=on failure of a node, the replacement node connects to any d of the existing nodes, downloading at-most β symbols from each of them; and    dβ=repair bandwidth.
The curve (“optimal storage-bandwidth tradeoff curve”) defined by equation 1 shows that both α and β cannot be simultaneously minimized. Thus, regenerating codes corresponding to the extremal points on the tradeoff curve are referred to as minimum storage regenerating (MSR) codes and minimum bandwidth regenerating (MBR) codes. An MSR code is an MDS code that minimizes the amount of storage space consumption per node (i.e., α). For an MSR code, the repair bandwidth is expressed by:
                                          d            ⁢                                                  ⁢            β                    =                      α            +                                          (                                  k                  -                  1                                )                            ⁢              β                                      ,                              where            ⁢                                                  ⁢            α                    =                                    B              k                        .                                              (                  Equation          ⁢                                          ⁢          2                )            An MBR code is a code that minimizes repair bandwidth. For an MBR code, the repair bandwidth is expressed as dβ=α.
The “code rate” for an (n, k) erasure code is defined as k/n or k/(k+r), which represents the proportion of the systematic data in the total amount of stored data (i.e., systematic data plus parity data). An erasure code having a code rate k/n>0.5 is referred to as a high rate erasure code. This means that the coding scheme will require a relatively large amount of systematic nodes k as compared to parity nodes r. Conversely, a low-rate (k/n≤0.5) erasure code will require a relatively small amount of systematic nodes k as compared to parity nodes r. High-rate erasure codes can be desirable because they require less storage overhead than low-rate erasure codes for a given set of systematic data.